class Solution {
public:
    string reorganizeString(string s) {
        int hash[26] = { 0 };
        int m = s.size();
        int maxcount = 0;
        char maxval = ' ';
        for (auto ch : s)
        {
            if (maxcount < ++hash[ch - 'a'])
            {
                maxcount = hash[ch - 'a'];
                maxval = ch;





            }




        }
        if (maxcount > (m + 1) / 2)return "";
        string str(m, ' ');

        int index = 0;
        for (int i = 0; i < maxcount; i++)
        {
            str[index] = maxval;
            index += 2;
        }
        hash[maxval - 'a'] = 0;
        for (int i = 0; i < 26; i++)
        {
            for (int j = 0; j < hash[i]; j++)
            {
                if (index >= m)
                    index = 1;
                str[index] = i + 'a';
                index += 2;





            }






        }
        return str;






















    }
}; class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {

        int pre = 0;
        int nex = 0;
        int count = 1;
        for (int i = 0; i < nums.size() - 1; i++)
        {
            nex = nums[i + 1] - nums[i];
            if (pre >= 0 && nex < 0 || pre <= 0 && nex>0)
            {
                count++;
                pre = nex;



            }






        }
        return count;






    }
}; class Solution {
public:
    string optimalDivision(vector<int>& nums) {
        int m = nums.size();
        if (m == 1)
            return to_string(nums[0]);

        string str;
        if (m == 2)
        {
            str += to_string(nums[0]);
            str += '/';
            str += to_string(nums[1]);
            return str;
        }
        str += to_string(nums[0]);
        str += '/';
        str += '(';
        for (int i = 1; i < m; i++)
        {
            str += to_string(nums[i]);
            if (i != m - 1)
                str += '/';



        }
        str += ')';
        return str;










    }
}; class Solution {
public:
    int brokenCalc(int startValue, int target) {
        int count = 0;
        while (target > startValue)
        {


            if (target % 2 == 1)
            {
                target += 1;
                count++;
            }
            else
            {
                target /= 2;
                count++;


            }








        }

        return count + startValue - target;





    }
}; class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string str = to_string(n);
        int m = str.size();
        for (int i = m - 1; i > 0; i--)
        {
            if (str[i - 1] > str[i])
            {
                str[i - 1]--;
                m = i;
            }




        }
        for (int i = m; i < str.size(); i++)
        {
            str[i] = '9';
        }

        return stoi(str);







    }
}; class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int, int>hash;
        int maxcount = 0;
        int maxval = 0;
        for (auto e : barcodes)
        {
            if (maxcount < ++hash[e])
            {
                maxcount = hash[e];
                maxval = e;
            }

        }
        int index = 0;
        int res = barcodes.size();
        vector<int>result(res);
        for (int i = 0; i < maxcount; i++)
        {
            result[index] = maxval;
            index += 2;

        }
        hash.erase(maxval);

        for (auto [a, b] : hash)
        {
            for (int i = 0; i < b; i++)
            {

                if (index >= res)index = 1;
                result[index] = a;
                index += 2;



            }







        }
        return result;









    }
}; class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        sort(begin(costs), end(costs), [](const vector<int>& x1, const vector<int>& x2)
            {
                return (x1[0] - x1[1] < x2[0] - x2[1]);



            });

        int sum = 0;
        int m = costs.size() / 2;
        for (int i = 0; i < m; i++)
        {
            sum += costs[i][0] + costs[i + m][1];






        }
        return sum;




    }
}; class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++)
        {

            sum += nums[i];



        }
        int res = -1;
        if (sum < x)
        {
            return res;

        }
        sum -= x;
        int target = 0;
        int left = 0;
        int right = 0;
        for (right = 0; right < nums.size(); right++)
        {
            target += nums[right];
            while (target > sum)
            {
                target -= nums[left];
                left++;
            }
            if (target == sum)
                res = max(res, right - left + 1);





        }

        return res < 0 ? res : nums.size() - res;

    }
}; class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        int m = nums.size();
        if (m == 1)
            return true;
        for (int i = 0; i <= cover; i++)
        {
            cover = max(cover, i + nums[i]);
            if (cover >= m - 1)
                return true;








        }
        return false;








    }
}; class Solution {
public:
    bool isSubsequence(string s, string t) {
        int sptr = 0;
        int tptr = 0;
        while (sptr < s.size() && tptr < t.size())
        {
            if (s[sptr] == t[tptr])
            {
                sptr++;
            }
            tptr++;







        }
        if (sptr == s.size())return true;
        return false;







    }
}; class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = 0; i < nums.size(); i += 2)
        {
            sum += nums[i];





        }
        return sum;






    }
}; class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int sum = numBottles;
        int emptybottles = numBottles;
        while (emptybottles >= numExchange)
        {
            int x = emptybottles / numExchange;
            sum += x;
            emptybottles = emptybottles % numExchange;
            emptybottles += x;








        }
        return sum;







    }
}; class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int m = 0;
        for (int i = 0; i < flowerbed.size(); i++)
        {
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.size() - 1 || flowerbed[i + 1] == 0))
            {
                m++;
                flowerbed[i] = 1;




            }
            if (m >= n)

                return true;








        }
        return false;










    }
};